A data communications network oftentimes includes a plurality of stations which share a common, limited bandwidth channel to communicate with a processor. The processor can be realized by a mainframe computer, a minicomputer, etc. When two or more stations transmit data which overlap in time on the common channel, a collision of data occurs. To avoid or resolve such a collision, an access scheme is typically employed in the data communications network to control the data traffic. Collision resolution typically calls for the "colliding" stations, i.e., those stations whose data transmissions have collided, to retransmit their respective data in an order prescribed by the access scheme.
The performance of a data communications network which utilizes an access scheme is measured in terms of throughput and access delay. Throughput is defined as the percentage of time that data is transmitted "successfully", i.e., without any collision. Access delay is defined as the average time period that particular data remains at a station before successful transmission.
Of the many access schemes, two of the more widely-known ones are the time division multiple access (TDMA) scheme and the ALOHA scheme. In the TDMA scheme, each station transmits only during its preassigned time slots which repeat periodically. (For details on the TDMA scheme, see, for example, J. F. Hayes, Modeling and Analysis of Computer Communications Networks (New York: Plenum Press), 1984, page 111, which is hereby incorporated by reference.) Such a scheme provides a high throughput in situations where the data communications traffic is heavy. On the other hand, it imposes an unduly long access delay on the data communications in light traffic situations.
In the ALOHA scheme, each station transmits data whenever the station is ready. When a collision occurs, each colliding station retransmits after a randomized delay. (For details on the ALOHA scheme, see, for example, A. S. Tanenbaum, Computer Networks (New Jersey: Prentice-Hall), 1981, pages 257-259, which is hereby incorporated by reference.) In contrast to the TDMA scheme, the ALOHA scheme affords a relatively short access delay in light traffic situations, but an undesirably low throughput in heavy traffic ones.
Many of other access schemes in the prior art are, to some extent, derived from the two aforementioned schemes. Specifically, they mimic the ALOHA scheme in light traffic situations and the TDMA scheme in heavy traffic ones. An example of such an access scheme is described in M. Sarraf and V. Li, "A Stable Multiple Access Scheme for Satellite Communications Networks," Proceedings of the IEEE-INFOCOM, April, 1986, which is hereby incorporated by reference. This scheme is hereinafter referred to as the Sarraf and Li scheme. In this scheme, newly generated data in each station is transmitted whenever the station is ready. When a collision occurs, each colliding station retransmits data during its preassigned time slots. Each colliding station also continues to transmit in its preassigned time slots until all of the remaining data in the station has been successfully transmitted. At such time, Each colliding station returns to its previous operational mode where data is transmitted whenever the station is ready.
The Sarraf and Li scheme desirably responds to a continuum of traffic volumes. That is, it continuously adjusts to new traffic conditions so as to effectively maintain a smooth traffic flow. In terms of performance, this scheme imposes a reasonable access delay on the data traffic, but it, nevertheless, provides an undesirably low throughput.
There are, however, other access schemes, for example, the urn protocol and the group testing scheme, which unlike the Sarraf and Li scheme, offer relatively high throughputs in addition to reasonable access delays. The urn protocol and the group testing scheme are respectively discussed in, A. S. Tanenbaum, Computer Networks (New Jersey: Prentice-Hall), 1981, pages 303-306; and T. Berger, et al., "Random Multiple-Access Communication and Group Testing," IEEE Trans. Commun., Vol. COM-32, July 1984, pages 769-779; both of which are hereby incorporated by reference. The urn protocol is, however, undesirable in networks where the bandwidth is in significant demand, which is normally the case. Specifically, in order for the urn protocol to operate, each of the stations in the data communications network must be continuously informed of a current estimate of the number of colliding stations to appropriately respond to the traffic condition. This being so, the urn protocol disadvantageously requires a separate subchannel to communicate such estimates to the stations.
The group testing scheme also has shortcomings. One such shortcoming is that it is incapable of responding to a continuum of traffic volumes. Specifically, under the group testing scheme, each station must store an internal table for each traffic volume. Since each station has a limited memory capacity, it can only store a finite number of internal tables. The actual number of internal tables stored, of course, depends on the size of the tables themselves. Furthermore, as is well known, the size of each table varies directly with the number of stations in the data communications network. As such, the group testing scheme can only respond to a finite number of traffic volumes, which number diminishes as the number of stations increases.
In view of the foregoing, it would be desirable to have an access scheme which not only offers a high throughput and a short access delay, but is also easy to implement and is responsive to a continuum of traffic volumes.